#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <map>
#include <list>
#include <algorithm>
#include <functional>
#include <unordered_map>
//#include <tr1/thread>
using namespace std;

struct Node
{
        char val;
        Node* next;
        Node(char v):val(v),next(NULL){}
        Node(char v,Node* n):val(v),next(n){}
};


bool isPlaindromeList(Node* pHead)
{
	if(!pHead)return false;
	if(!pHead->next)return true;
	Node* slow = pHead;
	Node* fast = pHead;
	stack<Node*> stk;
	//find the middle node
	while(fast && fast->next)
	{
		stk.push(slow);
		slow = slow->next;
		fast = fast->next->next;
	}
	if(fast != NULL)slow = slow->next;
	//compare the node of the left side with the right side
	while(!stk.empty())
	{
		Node* pLeft = stk.top();
		stk.pop();
		if(pLeft->val != slow->val)
			return false;
		slow = slow->next; 
	}
	return true;
}

int main(int argc, char const *argv[])
{
	//test cases
	//NULL
	//a
	//a->b
	//a->b->c
	//a->b->c->d
	//a->b->c->d->e
	Node* a=new Node('a',NULL);
	Node* b = new Node('b',NULL);
	Node* c = new Node('c',NULL);
	a->next =b ;
	b->next = c;
	cout<<isPlaindromeList(a)<<endl;
	return 0;
}